HEBCTF-easy_RSA¶
题目代码
¶
from gmpy2 import * from Crypto.Util import number #e = have a try~ p = number.getPrime(1024) q = number.getPrime(1024) nothing = 251560377963038761190200797029988859033 # getPrime(128) n = p*q fn = (p-1)*(q-1) d =inverse(e, fn) something=(p-1)d+nothing enc = pow(flag, e, p*q) print (n) #n=14284898343409519110893988467316511926370451139898930447913929171639157662416924629721731319745621456628886461208084701377746738712806909510733763533111440296587773645965346813837315287791601828684827959213005394017782134099259170149915437025962624405554913909119787918969678680969013413675883687099548278972115691260909326823826733899687527221094134484324195895781497056688836390217827814939835994217942643008875830529445666479044655104422017227768913567208280346040068940328073829553819676484041944265736136407848750757258471249497666545068872011229067294045688552723745158600169354377516976789338341197514239514943 print(s) #something=286513783515614922964487317633030845022199764334523704172857900468207328275601546483407711018702750569030377856457729134725585035340273850696372794971562057097878568322145360455616114805337204320995794956912354651091693657156422658881160865975268727450032165425473533693410304381371095831091118583746948774725405739487325458903660189348971842364607739242225293967215501191421774709879078076074161789004913628127600135108988375932151821980659991278616990695976636258955726402697510230023838942094639019441749484792888646404524697026596867444210593464034174763857812793583906156073077832265794741963441612539965049158860120119167347530684129840646220683525848056119433617113962506545054683798313759769240061077256966777326661431711874356368294140866366364716767053776009140934309044595124213623948792672967896390820967208318303287692916619220370506456013211642234660990531096377697018415439879456848769444607806947569088449625 print(enc) #enc=4881342612605167945566362034399587836635894621851547317823874228263412784935124440289546702719504165280607577300320293348921200397520285704213654018930232712940345612671113541266347784516634193958010265082924711886924437824841465114124020180216977559637341458252243825701112061216139287782944762861273904099742150098423639841865509382899243178009016015415485229031954926669538913188143653236257937229799801229863924027941144675212479223330496722053292471015086437410831685022807918456036289520338369388719529672585641297779845250083115247220743517626420017412100344704837819753505113936564984505444789009239645210810
代码分析
¶
- 1、代码中没有给出e的值,猜测是常见的e值,尝试了
65535
、65537
。 - 2、代码中给出了d和p的关系,因此可利用
费马小定理
求解。
【费马小定理】如果p是一个质数,而整数a不是p的倍数,则有a^(p-1)≡1 mod p
。
解题过程
¶
1、我们可以设A = m^(p-1)-1
,其中m^(p-1) ≡ 1 mod p
,故A是p的倍数,由于N = p*q
,因此gcd(A,N)=p
。
2、由m^e ≡ c mod N得到 c = m^e - b*N(b是整数)。
3、又因为 c^d ≡ m mod N
,所以(m^e - b*N)^d = m mod N
,进一步(m^e)^d = m mod N
。
4、等式两边取p-1
次方,得到:(m^ed)^(p-1) mod N = m^(p-1) mod N
,即:m^e(s-n) mod N = m^(p-1) mod N
。
5、得到A = (m^e(s-n) mod N)-1
,即可求得p = gcd(A,N)
。
代码如下
¶
import gmpy2 from Crypto.Util.number import * n=14284898343409519110893988467316511926370451139898930447913929171639157662416924629721731319745621456628886461208084701377746738712806909510733763533111440296587773645965346813837315287791601828684827959213005394017782134099259170149915437025962624405554913909119787918969678680969013413675883687099548278972115691260909326823826733899687527221094134484324195895781497056688836390217827814939835994217942643008875830529445666479044655104422017227768913567208280346040068940328073829553819676484041944265736136407848750757258471249497666545068872011229067294045688552723745158600169354377516976789338341197514239514943 enc=4881342612605167945566362034399587836635894621851547317823874228263412784935124440289546702719504165280607577300320293348921200397520285704213654018930232712940345612671113541266347784516634193958010265082924711886924437824841465114124020180216977559637341458252243825701112061216139287782944762861273904099742150098423639841865509382899243178009016015415485229031954926669538913188143653236257937229799801229863924027941144675212479223330496722053292471015086437410831685022807918456036289520338369388719529672585641297779845250083115247220743517626420017412100344704837819753505113936564984505444789009239645210810 something=286513783515614922964487317633030845022199764334523704172857900468207328275601546483407711018702750569030377856457729134725585035340273850696372794971562057097878568322145360455616114805337204320995794956912354651091693657156422658881160865975268727450032165425473533693410304381371095831091118583746948774725405739487325458903660189348971842364607739242225293967215501191421774709879078076074161789004913628127600135108988375932151821980659991278616990695976636258955726402697510230023838942094639019441749484792888646404524697026596867444210593464034174763857812793583906156073077832265794741963441612539965049158860120119167347530684129840646220683525848056119433617113962506545054683798313759769240061077256966777326661431711874356368294140866366364716767053776009140934309044595124213623948792672967896390820967208318303287692916619220370506456013211642234660990531096377697018415439879456848769444607806947569088449625 nothing=251560377963038761190200797029988859033 e = 65537 A=pow(2,e*something-e*nothing,n)-1 p = gmpy2.gcd(A,n) q = n // p d = gmpy2.invert(e,(p-1)*(q-1)) m = pow(enc, d, n) flag = long_to_bytes(m) print(flag)